package random;

/**
 * 托普利茨矩阵
 * 给你一个 m x n 的矩阵 matrix 。如果这个矩阵是托普利茨矩阵，返回 true ；否则，返回 false 。
 * 如果矩阵上每一条由左上到右下的对角线上的元素都相同，那么这个矩阵是 托普利茨矩阵
 *
 * 提示：
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 20
 * 0 <= matrix[i][j] <= 99
 *
 * 进阶：
 * 如果矩阵存储在磁盘上，并且内存有限，以至于一次最多只能将矩阵的一行加载到内存中，该怎么办？
 * 如果矩阵太大，以至于一次只能将不完整的一行加载到内存中，该怎么办？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/toeplitz-matrix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class L766 {
    public static void main(String[] args) {

//        int matrix[][] = {{1,2,3,4},{5,1,2,3},{9,5,1,2}};   //true
//        int matrix[][] = {{1,2},{2,2}};                     //false
//        int matrix[][] = {{18},{66}};                       //true
        int matrix[][] = {{11,74,0,93},{40,11,74,7}};         //false
        boolean toeplitzMatrix = isToeplitzMatrix(matrix);
        System.out.println(toeplitzMatrix);
    }

    public static boolean isToeplitzMatrix(int[][] matrix) {

        // 遍历每行每个数据，如果是第一行或者是每行第一个不用判断
        // 然后和上一行的数据进行比较即可
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if (i != 0 && j != 0){
                    if (matrix[i][j] != matrix[i-1][j-1]) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}


/*
对于进阶问题一，一次最多只能将矩阵的一行加载到内存中，我们将每一行复制到一个连续数组中，
随后在读取下一行时，就与内存中此前保存的数组进行比较。

对于进阶问题二，一次只能将不完整的一行加载到内存中，我们将整个矩阵竖直切分成若干子矩阵，
并保证两个相邻的矩阵至少有一列或一行是重合的，然后判断每个子矩阵是否符合要求。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/toeplitz-matrix/solution/tuo-pu-li-ci-ju-zhen-by-leetcode-solutio-57bb/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
